package tests;

public class Keyongyu {
    static class Node {
        String data;
        Node next;

        public Node(String data) {
            this.data = data;
        }

        @Override
        public String toString() {
            if (next == null) {
                return "Node{" + data + "}";
            }
            return "Node{" + data + "}->" + next;
        }
    }

    private static Node getRingFirst(Node head) {
        if(head == null || head.next == null){
            return null;
        }
        Node slow = head;
        Node fast = head;
        //找出相遇点
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
            if(slow == fast){
                break;
            }
        }

        if (fast == null || fast.next == null) {
            return null;
        } else {
            Node ptr1 = head;
            Node ptr2 = fast;
            while (ptr1 != ptr2) {
                ptr1 = ptr1.next;
                ptr2 = ptr2.next;
            }
            return ptr1;
        }
    }

    public static void main(String[] args) {
        Node circleLinkNode2 = buildNode(20, 5);
        System.out.println("环形第一个节点:" + getRingFirst(circleLinkNode2).data);
    }

    private static Node buildNode(int count, int ringIndex) {
        Node firstNode = null;
        Node firstCircleNode = null;
        Node pNode = null;
        for (int index = 1; index <= count; index++) {
            Node node = new Node("" + index);
            if (pNode != null) {
                pNode.next = node;
            }
            node.next = null;
            pNode = node;
            if (index == 1) {
                firstNode = node;
            }
            if (index == ringIndex) {
                firstCircleNode = node;
            }
        }
        pNode.next = firstCircleNode;
        return firstNode;
    }
}